﻿//
// Created by Administrator on 2025/7/7.
//

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <algorithm>
#include <functional>
#include "include/dongnaoedu_sort.hpp"
#include <windows.h>

using namespace std;
using namespace chrono;

// ================== 参数可调 ==================
const int N = 1000;        // 数组大小：可设置为 100、1000、10000、50000、100000 等
const int MAX_VAL = 99;    // 最大元素值（重要！如果使用 count_sort，不要超过 RANDMAX=100）
// ==============================================

/*
 * 排序算法性能对比（元素数量：100000，最大值：99）
----------------------------------------------
冒泡排序 用时：18984 ms
冒泡排序（优化） 用时：19982 ms
选择排序 用时：5386 ms
插入排序 用时：3588 ms
插入排序（二分） 用时：3275 ms
希尔排序 用时：12 ms
归并排序 用时：9 ms
快速排序 用时：6 ms
堆排序 用时：17 ms
计数排序 用时：0 ms
std::sort 用时：18 ms
 得出结论，选择快速排序是最好的选择
 * */

// 工具函数：生成随机整数数组
vector<int> generate_random_array(int size, int max_val = 100000) {
    SetConsoleOutputCP(CP_UTF8);  // 设置控制台编码为 UTF-8
    vector<int> arr(size);
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(0, max_val);

    for (int &x : arr)
        x = dis(gen);
    return arr;
}

// 测量排序函数执行时间（毫秒）
void measure(const string& name, function<void(vector<int>&)> sort_fn, const vector<int>& base) {
    vector<int> arr = base; // 保证每个算法使用相同的初始数据

    auto start = high_resolution_clock::now();
    sort_fn(arr);
    auto end = high_resolution_clock::now();

    auto duration = duration_cast<milliseconds>(end - start).count();
    cout << name << " 用时：" << duration << " ms" << endl;
}

// 包装模板排序函数，供 measure 使用
#define WRAP_SORT(fn) [&](vector<int>& v) { fn(v.data(), v.size()); }

int main() {
    vector<int> base = generate_random_array(N, MAX_VAL); // 为 count_sort 安全起见，max_val ≤ RANDMAX

    cout << "排序算法性能对比（元素数量：" << N << "，最大值：" << MAX_VAL << "）" << endl;
    cout << "----------------------------------------------" << endl;

    measure("冒泡排序", WRAP_SORT(bubble_sort), base);
    measure("冒泡排序（优化）", WRAP_SORT(bubble_sort_optimized), base);
    measure("选择排序", WRAP_SORT(select_sort), base);
    measure("插入排序", WRAP_SORT(insert_sort), base);
    measure("插入排序（二分）", WRAP_SORT(insert_sort_binary), base);
    measure("希尔排序", WRAP_SORT(shell_sort), base);
    measure("归并排序", WRAP_SORT(merge_sort), base);
    measure("快速排序", WRAP_SORT(quick_sort), base);
    measure("堆排序", WRAP_SORT(heap_sort), base);
    measure("计数排序", WRAP_SORT(count_sort), base);

    // 对比标准库排序
    measure("std::sort", [](vector<int>& v) { sort(v.begin(), v.end()); }, base);

    return 0;
}
